package main.Q201_300;

import java.util.*;

public class Q201_210 {
    public static void main(String[] args) {
        System.out.println("Question201：数字范围按位与");
        System.out.println("Question202：快乐数");
        System.out.println("Question203：移除链表元素");
        System.out.println("Question204：");
        System.out.println("Question205：同构字符串");
        System.out.println("Question206：反转链表");
        System.out.println("Question207：课程表");
        System.out.println("Question208：实现Trie(前缀树)");
        System.out.println("Question209：长度最小的子数组");
        System.out.println("Question210：课程表 II");
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Question201{
    public int rangeBitwiseAnd(int left, int right) {
        int offset=0;
        while (left!=right){
            left>>=1;
            right>>=1;
            offset++;
        }
        return right<<offset;
    }
}

class Question202{
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    public int getNext(int n){
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
}

class Question203{
    public ListNode removeElements(ListNode head, int val) {
        while(head!=null&&head.val==val){
            head=head.next;
        }
        if(head==null)
            return head;
        ListNode prev=head;
        //确保当前结点后还有结点
        while(prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else{
                prev=prev.next;
            }
        }
        return head;
    }
}

class Question205{
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();//建立2个map，两个字符串两相对应
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }
}

class Question206{
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

class Question207{
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses<=0) return false;
        int length= prerequisites.length;
        if (length==0) return true;
        int[] ins=new int[numCourses];//入度数
        HashSet<Integer>[] map=new HashSet[numCourses];//邻接矩阵
        for (int i=0;i<numCourses;i++) map[i]=new HashSet<>();
        for (int[] temp:prerequisites){//预处理，记录入度数与邻接矩阵
            ins[temp[0]]++;
            map[temp[1]].add(temp[0]);
        }
        Queue<Integer> queue=new LinkedList<>();
        for (int i=0;i<numCourses;i++){//将入度为0加入队列
            if (ins[i]==0){
                queue.add(i);
            }
        }
        int count=0;
        while (!queue.isEmpty()){
            Integer temp=queue.poll();
            count++;
            for (int num:map[temp]){//消除入度数
                ins[num]--;
                if (ins[num]==0){
                    queue.add(num);
                }
            }
        }
        return count==numCourses;
    }
}

class Trie{
    Trie[] children;
    boolean isEnd;
    public Trie() {
        children=new Trie[26];
        isEnd=false;
    }

    public void insert(String word) {
        Trie node=this;
        char[] str=word.toCharArray();
        for (int i=0;i<str.length;i++){
            int index=str[i]-'a';
            if (node.children[index]==null) node.children[index]=new Trie();
            node=node.children[index];
        }
        node.isEnd=true;
    }

    public boolean search(String word) {
        Trie node=searchPrefix(word);
        return node!=null&&node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix)!=null;
    }

    public Trie searchPrefix(String prefix){
        Trie node=this;
        char[] str=prefix.toCharArray();
        for (int i=0;i<str.length;i++){
            int index=str[i]-'a';
            if (node.children[index]==null) return null;
            node=node.children[index];
        }
        return node;
    }
}

class Question209{
    public int minSubArrayLen(int target, int[] nums) {
        int min=Integer.MAX_VALUE,left=0,right=0,sum=nums[0];
        while (left< nums.length){
            if (sum<target&&right!=nums.length-1){//当前窗口和小于target且右边界未达最右侧
                right++;
                sum+=nums[right];
            }else if (sum>=target){//当前窗口和大于等于target
                min=Math.min(min,right-left+1);
                sum-=nums[left];
                left++;
            }else if (right== nums.length-1){//窗口右边界到底，左边界移动
                sum-=nums[left];
                left++;
            }
        }
        return min==Integer.MAX_VALUE? 0:min;
    }
}

class Question210{
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Deque<Integer> queue=new LinkedList<>();
        int [] ins=new int [numCourses];//入度数
        int [] res=new int [numCourses];
        int cnt=0;//一个指针，表示res数组实际有的元素个数
        int n=prerequisites.length;
        for(int i=0;i<n;i++){
            ins[prerequisites[i][0]]++;
        }
        for(int i=0;i<numCourses;i++){//先找到没有入度的结点，入队
            if(ins[i]==0) queue.offer(i);
        }
        while(!queue.isEmpty()){
            int peek=queue.poll();//将队列中的队首元素出队
            res[cnt++]=peek;
            for(int []p:prerequisites){
                if(p[1]==peek){
                    ins[p[0]]--;
                    if(ins[p[0]]==0){
                        queue.offer(p[0]);
                    }
                }
            }
        }
        return cnt==numCourses ? res : new int [0];
    }
}